package Tree;

import java.util.*;

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    public static void main(String[] args) {
        TreeNode t = new TreeNode();
        List<Integer> datas = new LinkedList<>();
//        int [] datas= new int[7] [3,9,20,null,null,15,7];
//        datas = ;


    }

    TreeNode initTree(TreeNode root, List<Integer> datas) {
        //如果数组为空，返回空值
        if (datas.size() <= 0) return null;

        //借助队列实现非递归赋值
        Queue<TreeNode> trees = new LinkedList<>();
        //根节点入队
        root.val = datas.get(0);
        trees.add(root);
        int index = 0;
        while (index < datas.size() - 2) {

            TreeNode tParrent = trees.poll();

            if (++index <= datas.size()) {
                TreeNode leftTree = new TreeNode();
                leftTree.val = datas.get(index);
                tParrent.left = leftTree;
                trees.offer(leftTree);
            } else break;
            if (++index <= datas.size()) {
                TreeNode rightTree = new TreeNode();
                rightTree.val = datas.get(index);
                tParrent.right = rightTree;
                trees.offer(rightTree);
            } else break;
        }
        return root;
    }


/*
102. 二叉树的层序遍历
借助双端队列实现
还可用于计算树的深度
 */

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new LinkedList<>();
        if (root == null) return ans;
        Deque<TreeNode> q = new LinkedList<>();
        q.offerLast(root);
        TreeNode begin, end = root;
        boolean flag = false;
        List<Integer> layer = new LinkedList<>();

        while (q.isEmpty() != true) {
            TreeNode t = q.poll();
            layer.add(t.val);
            if (t.left != null) q.offer(t.left);
            if (t.right != null) q.offer(t.right);
            if (t == end) {
                end = q.peekLast();

                if (flag) {
                    Collections.reverse(layer);
                }
                flag = !flag;
                ans.add(layer);
                layer = new LinkedList<>();
            }
        }
        return ans;
    }

    int minDepth(TreeNode root) {
        if (root == null) return 0;
        Stack<TreeNode> s = new Stack<TreeNode>();
        s.push(root);
        int min = 100001;
        List<TreeNode> visited = new LinkedList<>();
        while (!s.empty()) {
            TreeNode sPeek = s.peek();
            if (sPeek.left != null && !visited.contains(sPeek.left)) {
                s.push(sPeek.left);
            } else if (sPeek.right != null && !visited.contains(sPeek.right)) {
                s.push(sPeek.right);
            } else {
                if (min > s.size()) min = s.size();
                visited.add(s.pop());
            }
        }
        return min;
    }

}
